---
title: "7、基德的密码锁"
created: 2025-11-28
tags:
  - 算法
---

# 7、基德的密码锁

## 题目 [基德的密码锁](https://www.lanqiao.cn/problems/4150/learning/)

![[image-7a59331f.png]]

## 思路分析

第一眼也是发现可以用指数型枚举dfs去写

但是数据范围是1000 那明显就是要把dfs改成dp了

状态表示：第i个位置 选j的方案总数

属性：count

状态计算：上一个数 选1~j-k 和 j+k~m的方案数之和

![[image-65648042.png]]

只能过1/3 6分

优化暂时没想到

可能可以用前缀和 但是结合在dp过程中 代码难度就上去了 不敢保证写对 可能全改错了 不值得冒这个风险

## 代码实现

朴素  5/15

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

//感觉可以指数型枚举的写法 但是数据范围是1000 那应该是dfs改dp

const int N=1010,M=5010,mod=998244353;

LL f[N][M];//第i个位置 选j的方案总数 count

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n,m,k;

    cin>>n>>m>>k;

    for(int i=1;i<=m;i++)

        f[1][i]=1;//第一个位置可以选任何数 有一种方案

    for(int i=2;i<=n;i++){

        for(int j=1;j<=m;j++){

            if(j-k>=1){

                for(int c=1;c<=j-k;c++){

                    f[i][j]=(f[i][j]+f[i-1][c])%mod;

                }

            }

            if(j+k<=m){

                for(int c=j+k;c<=m;c++){

                    f[i][j]=(f[i][j]+f[i-1][c])%mod;

                }

            }

        }

    }

    LL res=0;

    for(int i=1;i<=m;i++){

        res=(res+f[n][i])%mod;

    }

    cout<<res;

    return 0;

}
```

前缀和优化 ac

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef long long LL;

const int N=1010,M=5010,mod=998244353;

LL f[N][M];

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n,m,k;

    cin>>n>>m>>k;

    for(int i=1;i<=m;i++)

        f[1][i]=1;

    for(int i=2;i<=n;i++){

    	for(int j=1;j<=m;j++)

    		f[i-1][j]=(f[i-1][j]+f[i-1][j-1])%mod;

        for(int j=1;j<=m;j++){

            if(j-k>=0)

                f[i][j]=(f[i][j]+f[i-1][j-k])%mod;

            if(k==0)

            	f[i][j]=(f[i][j]+f[i-1][m]-f[i-1][min(m,j+k)]+mod)%mod;

            else

                f[i][j]=(f[i][j]+f[i-1][m]-f[i-1][min(m,j+k-1)]+mod)%mod;

            f[i][j]%=mod;

        }

    }

    LL res=0;

    for(int i=1;i<=m;i++){

        res=(res+f[n][i])%mod;

    }

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[6、七彩之城的独特序列|6、七彩之城的独特序列]] 🏠 [[00-刷题理模型]] ➡️ [[8、完美队列的数目|8、完美队列的数目]]